﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//看到题目有两种思路
//1，先序遍历的结果是一个升序数组
//2，递归判断左右子树和中间的关系

class Sol98
{
    //不要一次判断三个树的关系，分别判断两个子树和父亲的 关系
    public bool IsValidBST2(TreeNode root)
    {

        return isSearchTree(root, long.MinValue, long.MaxValue);
    }

    public bool isSearchTree(TreeNode root, long lower, long upper)
    {



        if (root == null) return true;

        if(root.val< upper&& root.val > lower)
        {


           return    isSearchTree(root.left, lower,  root.val)&&isSearchTree(root.right, root.val, upper);
            
        }
        else
        {
            return false;
        }
 
    }

    public bool IsValidBSTrecursion(TreeNode root)//这个方法可以升级一下，需要存结果，在遍历过程中判断大小关系就可以了
    {
        //int[] inOreder=new int[2];
        List<int> inOreder=new List<int>();
        //中序遍历一下
        Inorder(root,inOreder);

        if(inOreder.Count == 1)
        {
            return true;
        }

        for (int i=1;i<inOreder.Count;i++)
        {
            if (inOreder[i]<= inOreder[i - 1])
            {
                return false;
            }


        }
        return true;
    }

    private void Inorder(TreeNode root, List<int> inOreder)
    {
       if(root == null) return;

       Inorder(root.left, inOreder);
        inOreder.Add(root.val);

        Inorder(root.right, inOreder);
    }

    public bool IsValidBST(TreeNode root)//递归法中序遍历
    {

        if (root == null) return true;
        long val = long.MinValue;

        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (root != null || stack.Count > 0)
        {


            while (root != null)
            {
                stack.Push(root);
                root = root.left;
            }

            root = stack.Pop();
            if (root.val > val)
            {
                val = root.val;
            }
            else
            {
                return false;
            }


            root = root.right;


        }
        return true;
    }


    }
class Program98
{

    static void Main98(string[] args)
    {
        //先读取输入
        //string s=Console.ReadLine();
        string s = "2 2 2";
        string[] chars= s.Split(" ");
        int[] nums =new int[chars.Length];
        for (int i=0; i<chars.Length; i++)
        {
            nums[i]= int.Parse(chars[i]);   
        }

        //for (int i = 0; i < nums.Length; i++)
        //{
        //    Console.WriteLine(nums[i]);
        //}



        int[] inOrder = { 2, 2, 2 };
        Solution105 solution105 = new Solution105();

       

        TreeNode root = solution105.BuildTree(nums, inOrder);

        //solution105.levelOrder(root);

        Sol98 ss = new Sol98();
       bool res= ss.IsValidBST(root);
        Console.WriteLine(res);
    }
}